package com.lp;

public class Fibonacci {
    public static void main(String[] args) {
//        long l = System.currentTimeMillis();
//        long i = fib1(50);
//        long l1 = System.currentTimeMillis();
//        long lw = System.currentTimeMillis();
        long lw = System.nanoTime();

        long w = fib3(6000, 1, 1);
//        long lw1 = System.currentTimeMillis();
        long lw1 = System.nanoTime();
//        System.out.println("递归法："+i);
        System.out.println("尾递归："+w);
//        System.out.println("递归法："+(l1-l));
        System.out.println("尾递归："+(lw1-lw));
        long l2 = System.currentTimeMillis();
        long i1 = fib2(6000);
//        for(int y=0;y<1000000000;y++){
//            if(y==9999){
//                System.out.println(y);
//            }
//        }
        long l3 = System.currentTimeMillis();
        System.out.println("动态规划："+i1);
        System.out.println("动态规划："+(l3-l2));
    }
    //递归法
    public static long fib1(int x){
        long res = 0;
        if(x == 1 || x == 2){
            return 1;
        }else{
            res = fib1(x-1)+fib1(x-2);
            return res;
        }
    }
    //尾递归实现
    public static long fib3(int x, long a, long b){
        if(x <= 1){
            return a;
        }else{
            return fib3(x-1,b,a+b);
        }
    }
    //动态规划法
    public static long fib2(int x){
        if(x==1 || x==2){
            return 1;
        }else{
            long first = 1;
            long second = 1;
            long third = 0;
            for(int i=3; i<=x;i++){
                third = first + second;
                first = second;
                second = third;
            }
            return third;
        }
    }
}
